package middle;

import java.util.Stack;

public class Solution_402 {

    public static void main(String[] args) {
        Solution_402 model = new Solution_402();
        System.out.println(model.removeKdigits("1432219", 3));
        System.out.println(model.removeKdigits("10200", 1));
        System.out.println(model.removeKdigits("10", 2));
        System.out.println(model.removeKdigits("1234567890", 9));
    }

    public String removeKdigits(String num, int k) {
        char[] chars = num.toCharArray();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            int n = chars[i] - '0';
            if (k <= 0 || stack.empty() || stack.peek() <= n) {
                stack.add(n);
            } else {
                while (!stack.empty() && stack.peek() > n && k > 0) {
                    stack.pop();
                    k--;
                }
                stack.add(n);
            }
        }
        while (k > 0) {
            stack.pop();
            k--;
        }
        int last = 0;
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            if (stack.peek() != 0) {
                last = builder.length() + 1;
            }
            builder.append(stack.pop());
        }
        return last == 0 ? "0" : builder.reverse().substring(builder.length() - last);
    }
}
